﻿#include <iostream>
#include <vector>
#include <string>

using namespace std;

/*
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
 

示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"

解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：
输入：s = "A", numRows = 1
输出："A"
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/


////模拟
//class Solution {
//public:
//	string v[1010];
//	string convert(string s, int numRows) {
//		if (s.size() <= 1 || 1 == numRows)return s;
//		int idx = 0;
//		while(idx < s.size()){
//			for (int i = 0; i < (numRows * 2 - 2); i++) {
//				if (i < numRows) {
//					v[i]+=(s[idx]); idx++;
//				}
//				else {
//					v[(numRows * 2 - 2) - i]+=(s[idx]); idx++;
//				}
//				if (idx >= s.size()) break;
//			}
//		}
//
//		string ans;
//		for (int i = 0; i < numRows; i++) {
//			ans += v[i];
//		}
//		return ans;
//	}
//};
 

class Solution {
public:
	void Add(int i, const string&s, string& ans) {
		if (i >= s.size()) return;
		ans += s[i];
	}

	string convert(string s, int numRows) {
		if (s.size() <= 1 || numRows == 1) return s;
		string ans;
		for (int i = 0; i < numRows; i++) {
			Add(i, s, ans);
			if (i == 0 || i == numRows - 1) {
				int idx1 = i+ (numRows*2-2);
				while (idx1 < s.size()) {
					Add(idx1, s, ans);
					idx1 += (numRows*2-2);
				}
			}
			else {
				int idx1 = i+(numRows*2-2); int idx2 = (numRows * 2 - 2 - i);
				while (idx1 < s.size() || idx2 < s.size()) {
					if (idx2 < s.size()) {
						Add(idx2, s, ans);
						idx2 += (numRows * 2 - 2);
					}
					if (idx1 < s.size()) {
						Add(idx1, s, ans);
						idx1 += (numRows*2-2);
					}
				}	
			}
		}
		return ans;
	}
};

//int main() {
//	Solution s;
//	cout << s.convert("ab", 3) << endl;
//	return 0;
//}